/*
 * Copyright (C) 2009,2010,2011  Paulo Cesar Pereira de Andrade.
 *
 * This is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * Authors:
 *	Paulo Cesar Pereira de Andrade
 */

#include "exl.h"

#define NOTE_INC				16
#define LINE_INC				16
#define PAIR_INC				64

/*
 * Prototypes
 */
static eint32_t
note_insert_index(eint8_t *code);

static eint32_t
note_search_index(eint8_t *code);

static void
new_line(enote_t *note, evector_t *name, eint32_t lineno, eint32_t offset);

static eint32_t
line_insert_index(enote_t *note, eint32_t offset);

static eint32_t
line_search_index(enote_t *note, eint32_t offset);

static eint32_t
offset_insert_index(eline_t *note, eint32_t offset);

static eint32_t
offset_search_index(eline_t *note, eint32_t offset);

/*
 * Initialization
 */
enote_t		*note_vector;
eint32_t	 note_count;

/*
 * Implementation
 */
void
init_note(void)
{
}

void
finish_note(void)
{
    if (note_count & (NOTE_INC - 1))
	eresize_object((eobject_t *)&note_vector,
		       sizeof(enote_t) * note_count);
}

void
enew_note(eobject_t *pointer, eint8_t *base, evector_t *name)
{
    enote_t	*note;
    eint32_t	 index;

    /* allocate memory for new note */
    if (note_vector == null)
	enew_object((eobject_t *)&note_vector, t_resize | t_void,
		    NOTE_INC * sizeof(enote_t));
    else if ((note_count & (NOTE_INC - 1)) == 0)
	eresize_object((eobject_t *)&note_vector,
		       sizeof(enote_t) * (note_count + NOTE_INC));

    /* find insertion index */
    index = note_insert_index(base);

    /* insert note */
    if (index < note_count)
	memmove(note_vector + index + 1, note_vector + index,
		sizeof(enote_t) * (note_count - index));
    note = note_vector + index;
    ++note_count;

    *pointer = note;
    note->code = base;
    note->name = name;
    note->lines = null;
    note->count = 0;
}

void
eset_note(enote_t *note, eint32_t length)
{
    note->length = length;
}

void
efinish_note(enote_t *note)
{
    eline_t	*line;
    eint32_t	 offset;

    for (offset = note->count, line = note->lines; offset; offset--, line++) {
	if (line->count & (PAIR_INC - 1)) {
	    eresize_object((eobject_t *)&line->linenos,
			   sizeof(eint32_t) * line->count);
	    eresize_object((eobject_t *)&line->offsets,
			   sizeof(eint32_t) * line->count);
	}
    }
    if (note->count & (LINE_INC - 1))
	eresize_object((eobject_t *)&note->lines,
		       sizeof(eline_t) * note->count);
}

void
eannotate(enote_t *note, evector_t *name, eint32_t lineno, eint32_t offset)
{
    eline_t	*line;
    eint32_t	 index;

    /* if there isn't a note at this offset, or it would match another name */
    index = line_insert_index(note, offset);
    if (index >= note->count || note->lines[index].name != name)
	new_line(note, name, lineno, offset);
    else {
	line = note->lines + index;
	index = offset_insert_index(line, offset);
	if (line->offsets[index] == offset) {
	    /* this may happen if there are several comment lines,
	     * that is, no code was generated for several lines */
	    if (line->linenos[index] < lineno)
		line->linenos[index] = lineno;
	}
	else if (line->linenos[index] == lineno) {
	    /* check if need to extend entry */
	    if (line->offsets[index] > offset)
		line->offsets[index] = offset;
	}
	else {
	    /* line or offset changed, insert new entry */
	    if ((line->count & (PAIR_INC - 1)) == 0) {
		eresize_object((eobject_t *)&line->linenos,
			       sizeof(eint32_t) * (line->count + PAIR_INC));
		eresize_object((eobject_t *)&line->offsets,
			       sizeof(eint32_t) * (line->count + PAIR_INC));
	    }
	    if (index < line->count) {
		memmove(line->linenos + index + 1, line->linenos + index,
			sizeof(eint32_t) * (line->count - index));
		memmove(line->offsets + index + 1, line->offsets + index,
			sizeof(eint32_t) * (line->count - index));
	    }
	    line->linenos[index] = lineno;
	    line->offsets[index] = offset;
	    ++line->count;
	}
    }
}

ebool_t
eget_note(eobject_t code, evector_t **f, evector_t **n, eint32_t *l)
{
    enote_t	*note;
    eline_t	*line;
    eint32_t	 index;
    eint32_t	 offset;

    if ((index = note_search_index(code)) >= note_count)
	goto fail;
    note = note_vector + index;
    if ((eint8_t *)code < note->code ||
	(eint8_t *)code >= note->code + note->length)
	goto fail;
    offset = (eint8_t *)code - note->code;
    if ((index = line_search_index(note, offset)) >= note->count)
	goto fail;
    line = note->lines + index;
    if ((index = offset_search_index(line, offset)) >= line->count)
	goto fail;

    if (f)					*f = note->name;
    if (n)					*n = line->name;
    if (l)					*l = line->linenos[index];
    return (true);

fail:
    if (f)					*f = null;
    if (n)					*n = null;
    if (l)					*l = 0;

    return (false);
}

static eint32_t
note_insert_index(eint8_t *code)
{
    eint32_t	 bot;
    eint32_t	 top;
    eint32_t	 index;

    bot = 0;
    top = note_count;
    for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
	if (code < note_vector[index].code)
	    top = index;
	else
	    bot = index + 1;
    }

    return ((bot + top) >> 1);
}

static eint32_t
note_search_index(eint8_t *code)
{
    eint32_t	 bot;
    eint32_t	 top;
    eint32_t	 index;

    bot = 0;
    top = note_count;
    for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
	if (code < note_vector[index].code)
	    top = index;
	else if (code >= note_vector[index].code &&
		 code - note_vector[index].code < note_vector[index].length)
	    break;
	else
	    bot = index + 1;
    }

    return (index);
}

static void
new_line(enote_t *note, evector_t *name, eint32_t lineno, eint32_t offset)
{
    eline_t	*line;
    eint32_t	 index;

    index = line_insert_index(note, offset);

    /* allocate space for new line */
    if (note->lines == null)
	enew_object((eobject_t *)&note->lines, t_resize | t_void,
		    LINE_INC * sizeof(eline_t));
    else if ((note->count & (LINE_INC - 1)) == 0)
	eresize_object((eobject_t *)&note->lines,
		       sizeof(eline_t) * (note->count + LINE_INC));

    /* insert line */
    if (index < note->count)
	memmove(note->lines + index + 1, note->lines + index,
		sizeof(eline_t) * (note->count - index));
    line = note->lines + index;
    ++note->count;

    /* add first entry */
    line->name = name;
    line->count = 1;
    enew_object((eobject_t *)&line->linenos, t_resize | t_int32,
		PAIR_INC * sizeof(eint32_t));
    line->linenos[0] = lineno;
    enew_object((eobject_t *)&line->offsets, t_resize | t_int32,
		PAIR_INC * sizeof(eint32_t));
    line->offsets[0] = offset;
}

static eint32_t
line_insert_index(enote_t *note, eint32_t offset)
{
    eint32_t	 bot;
    eint32_t	 top;
    eint32_t	 index;
    eline_t	*lines;

    bot = 0;
    top = note->count;
    if ((lines = note->lines) == 0)
	return (0);
    for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
	if (offset < *lines[index].offsets)
	    top = index;
	else
	    bot = index + 1;
    }

    return ((bot + top) >> 1);
}

static eint32_t
line_search_index(enote_t *note, eint32_t offset)
{
    eint32_t	 bot;
    eint32_t	 top;
    eint32_t	 index;
    eline_t	*lines;

    bot = 0;
    top = note->count;
    if ((lines = note->lines) == 0)
	return (0);
    for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
	if (offset < *lines[index].offsets)
	    top = index;
	/* offset should be already verified to be in range */
	else if (index == note->count - 1 ||
		 (offset >= *lines[index].offsets &&
		  offset < *lines[index + 1].offsets))
	    break;
	else
	    bot = index + 1;
    }

    return (index);
}

static eint32_t
offset_insert_index(eline_t *line, eint32_t offset)
{
    eint32_t	 bot;
    eint32_t	 top;
    eint32_t	 index;
    eint32_t	*offsets;

    bot = 0;
    top = line->count;
    offsets = line->offsets;
    for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
	if (offset < offsets[index])
	    top = index;
	else
	    bot = index + 1;
    }

    return ((bot + top) >> 1);
}

static eint32_t
offset_search_index(eline_t *line, eint32_t offset)
{
    eint32_t	 bot;
    eint32_t	 top;
    eint32_t	 index;
    eint32_t	*offsets;

    bot = 0;
    top = line->count;
    offsets = line->offsets;
    for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
	if (offset < offsets[index])
	    top = index;
	/* offset should be already verified to be in range */
	else if (index == line->count - 1 ||
		 (offset >= offsets[index] && offset < offsets[index + 1]))
	    break;
	else
	    bot = index + 1;
    }

    return (index);
}
